# 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。
# 判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和targetSum 。如果存在，返回 true ；否则，返回 false 。
#  叶子节点 是指没有子节点的节点。
#
#  示例 1：
# 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
# 输出：true
# 解释：等于目标和的根节点到叶节点路径如上图所示。
#
#  示例 2：
# 输入：root = [1,2,3], targetSum = 5
# 输出：false
# 解释：树中存在两条根节点到叶子节点的路径：
# (1 --> 2): 和为 3
# (1 --> 3): 和为 4
# 不存在 sum = 5 的根节点到叶子节点的路径。
#
#  示例 3：
# 输入：root = [], targetSum = 0
# 输出：false
# 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
from com.example.tree.tree_node import TreeNode
from typing import Optional


class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:  # 到了叶子节点，直接判断
            return targetSum == root.val
        # 判断左子树和右子树路径是否等于targetSum
        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)


if __name__ == "__main__":
    #                  5
    #         4                     8
    #     11                   13         4
    #  7      2                               1
    root = TreeNode(5)
    root.left, root.right = TreeNode(4), TreeNode(8)
    root.left.left, root.right.left, root.right.right = TreeNode(11), TreeNode(13), TreeNode(4)
    root.left.left.left, root.left.left.right, root.right.right.right = TreeNode(7), TreeNode(2), TreeNode(1)
    targetSum = 22
    print(Solution().hasPathSum(root, targetSum))
